# 线段树
# class NumArray(object):
#
#     def __init__(self, nums):
#         """
#         :type nums: List[int]
#         """
#         self.n = len(nums)
#         self.seg = [0] * (4 * self.n)
#         self.build(nums, 0, 0, self.n - 1)
#
#     def build(self, nums, node, e, s):
#         if e == s:
#             self.seg[node] = nums[e]
#             return nums[e]
#         else:
#             m = (e + s) // 2
#             left = self.build(nums, 2 * node + 1, e, m)
#             right = self.build(nums, 2 * node + 2, m + 1, s)
#             self.seg[node] = left + right
#             return self.seg[node]
#
#     def search(self, node, index, val, e, s):
#         if e == s:
#             prev = self.seg[node]
#             self.seg[node] = val
#             diff = val - prev
#             return diff
#         else:
#             m = (e + s) // 2
#             if index <= m:
#                 s = m
#                 next_node = 2 * node + 1
#             else:
#                 e = m + 1
#                 next_node = 2 * node + 2
#             diff = self.search(next_node, index, val, e, s)
#             self.seg[node] += diff
#             return diff
#
#     def update(self, index, val):
#         """
#         :type index: int
#         :type val: int
#         :rtype: None
#         """
#         self.search(0, index, val, 0, self.n - 1)
#
#     def search_sum(self, node, e, s, left, right):
#         m = (e + s) // 2
#         if e == left and s == right:
#             return self.seg[node]
#         if right <= m:
#             return self.search_sum(2 * node + 1, e, m, left, right)
#         if left > m:
#             return self.search_sum(2 * node + 2, m + 1, s, left, right)
#         return self.search_sum(2 * node + 1, e, m, left, m) + self.search_sum(2 * node + 2, m + 1, s, m + 1, right)
#
#     def sumRange(self, left, right):
#         """
#         :type left: int
#         :type right: int
#         :rtype: int
#         """
#         return self.search_sum(0, 0, self.n - 1, left, right)

# 树状树
class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums
        self.n = len(self.nums)
        self.tree = [0] * (len(self.nums) + 1)
        for i, num in enumerate(self.nums):
            self.add(i + 1, num)

    def add(self, index, diff):
        while index <= self.n:
            self.tree[index] += diff
            index += index & -index

    def search(self, index):
        num = 0
        while index > 0:
            num += self.tree[index]
            index &= index - 1
        return num

    def update(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        """
        pre = self.nums[index]
        self.nums[index] = val
        diff = val - pre
        self.add(index + 1, diff)

    def sumRange(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: int
        """
        return self.search(right + 1) - self.search(left)
